from collections import defaultdict
from functools import lru_cache
from typing import List


class Trie:
    def __init__(self):
        self.children = defaultdict(Trie)
        self.word = ""
        self.is_word = False

    def insert(self, word):
        cur = self
        w = ""
        for c in word:
            cur = cur.children[c]
            w += c
            cur.word = w
        cur.is_word = True


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # 构造字典树
        trie = Trie()
        for word in words:
            trie.insert(word)

        ans = set()

        m, n = len(board), len(board[0])

        def is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        def neighbors(x, y):
            return [(xx, yy) for xx, yy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] if is_valid(xx, yy)]

        # 深度优先搜索
        @lru_cache(None)
        def dfs(now, i1, j1):
            if board[i1][j1] not in now.children:
                return

            ch = board[i1][j1]

            now = now.children[board[i1][j1]]

            board[i1][j1] = "#"

            if now.is_word:
                ans.add(now.word)

            for i2, j2 in neighbors(i1, j1):
                dfs(now, i2, j2)

            board[i1][j1] = ch

        # 遍历二维网格
        for i in range(m):
            for j in range(n):
                dfs(trie, i, j)

        return list(ans)


if __name__ == "__main__":
    # ["eat","oath"]
    print(Solution().findWords(
        board=[["o", "a", "a", "n"], ["e", "t", "a", "e"], ["i", "h", "k", "r"], ["i", "f", "l", "v"]],
        words=["oath", "pea", "eat", "rain"]))

    # []
    print(Solution().findWords(board=[["a", "b"], ["c", "d"]], words=["abcb"]))

    # ["a"]
    print(Solution().findWords(board=[["a"]], words=["a"]))

    # []
    print(Solution().findWords(board=[["a", "a"]], words=["aaa"]))
